

			LA CINEMA
		       -----------

	Un grup de n prieteni se duc la cinema. Fiecare dintre ei si-a cumparat bilet separat, insa
conform intelegerii initiale toti si-au luat bilet pe randul 17. Ajungand dupa inceputul filmului,
ei se aseaza la intamplare pe acest rand. Fiecare dintre cei n prieteni considera ca locul de pe
biletul sau este cel mai bun, asa ca fiecare doreste sa ajunga pe locul sau. Pentru a nu deranja
prea tare restul spectatorilor ei se hotarasc ca in fiecare minut, mai multe perechi de persoane
sa-si schimbe locul intre ele. La fiecare minut, numarul de schimbari poate fi oricat de mare,insa
o persoana nu poate participa decat la o singura astfel de schimbare.
	Aflati numarul minim de minute necesare pentru ca fiecare persoana sa ajunga pe locul sau.
	Pentru simplificare, consideram ca persoana 1 are biletul cu locul 1, persoana 2 are bile-
tul cu locul 2 s.a.m.d.

DATE DE INTRARE:
	Datele de intrare se citesc din fisierul CINEMA.IN. Pe prima linie este scris numarul n
(n<=1000) de prieteni care merg la cinema. Pe fiecare din urmatoarele n linii se afla cate un numar,
reprezentand locurile pe care prietenii s-au asezat initial.

DATE DE IESIRE:
	Datele de iesire se scriu in fisierul CINEMA.OUT. Prima linie a acestui fisier va contine
numarul minim M de minute necesare pentru ca fiecare persoana sa ajunga la locul sau.

Urmeaza M blocuri cu urmatoarea structura:
- prima linie a blocului contine numarul R de mutari care sunt executate la minutul respectiv
- urmatoarele R linii contin perechi de numere (i,j), separate printr-un spatiu, avand semnifica-
tia: in minutul respectiv, persoana i isi schimba locul cu persoana j.

EXEMPLU:
CINEMA.IN		CINEMA.OUT
3			2
3			1
1			1 2
2			1
			2 3